/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-62-不同路径
 * @date 2025/8/21 16:34
 */
public class Solution62 {
    /**
     * bfs超时
     */
    /*
    private int ans = 0;
    private int xBound;
    private int yBound;

    public int uniquePaths(int m, int n) {
        int i = 0, j = 0;
        xBound = m - 1;
        yBound = n - 1;
        bfs(0, 0);
        return ans;
    }

    private void bfs(int x, int y) {
        if (x > xBound || y > yBound) {
            return;
        } else if (x == xBound && y == yBound) {
            ans++;
            return;
        }
        bfs(x, y + 1);
        bfs(x + 1, y);
    }*/

    /**
     * dp解法
     * @param m
     * @param n
     * @return
     */
    /*public int uniquePaths(int m, int n) {
        int[][] paths = new int[m][n];
        paths[m - 1][n - 1] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j == n - 1) {
                    continue;
                }
                int right = 0, low = 0;
                if (i + 1 < m) {
                    low = paths[i + 1][j];
                }
                if (j + 1 < n) {
                    right = paths[i][j + 1];
                }
                paths[i][j] = right + low;
            }
        }
        return paths[0][0];
    }*/

    /**
     * dp解法，进一步优化空间复杂度
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[] paths = new int[n];
        paths[n - 1] = 1;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int right = 0;
                if (j + 1 < n) {
                    right = paths[j + 1];
                }
                paths[j] += right;
            }
        }

        return paths[0];
    }
}
